Apprentissage par différences temporelles (Temporal-Difference - TD)¶
2. Prédiction par différences temporelles¶
2.1. Retour sur la méthode de Monte-Carlo
Tout comme les méthodes de Monte-Carlo, les méthodes par différences temporelles utilisent des résultats d'expériences pour réaliser des prédictions. En se basant sur ces résultats obtenus en suivant une stratégie $\pi$, ces méthodes mettent à jour l'estimation de leurs valeurs d'états pour chacun des états de l'environnement. Avec la méthode de Monte-Carlo, elles attendent la fin d'un épisode pour mettre à jour les valeurs des états en utilisant la moyenne des revenus obtenus.
Cette idée peut être formulée par l'équation suivante. Si on appelle $R_i$ la récompense obtenue suite à l'itération $i$ qui suit l'action $a$ prise sur un état $s$, alors le revenu moyen $Q_n$ obtenu à la fin de l'épisode est:
De là, on peut chercher une relation de récurrence pour exprimer le revenu :
$\large{Q_{n + 1}} = \frac{1}{n}\sum\limits_{i = 1}^n {{R_i}} = \frac{1}{n}\left( {\sum\limits_{i = 1}^{n - 1} {{R_i}} + {R_n}} \right)$
$\large\quad\quad\quad= \frac{1}{n}\left( {\left( {n - 1} \right)\frac{1}{{n - 1}}\sum\limits_{i = 1}^{n - 1} {{R_i}} + {R_n}} \right) = \frac{1}{n}\left( {\left( {n - 1} \right){Q_n} + {R_n}} \right)$
$\large\quad\quad\quad=\frac{1}{n}\left( {n{Q_n} - {Q_n} + {R_n}} \right)$
$\large{Q_{n + 1}}={Q_n} + \frac{1}{n}\left( {{R_n} - {Q_n}} \right)$
Cette expression est de la forme générale:
Nouvelle estimation = Ancienne estimation + (pas de calcul)*[Cible - Ancienne estimation] ¶
La nouvelle estimation est donc calculée en ajoutant à l'ancienne estimation une proportion de l'erreur d'estimation ([Cible - Ancienne estimation]). On montre que dans le cas où les système étudiées sont non stationnaires, comme c'est très souvent le cas dans les situations rencontrées en apprentissage automatique, la manière dont cette proportion est ajoutée (le coefficient pas de calcul) doit être une constante $0 < \alpha < 1$. La convergence dans ce cas n'est pas complètement assurée mais la rapidité d'apprentissage est beaucoup plus rapide qu'avec une condition telle que $\alpha = \frac{1}{n}$.
Cette relation permet de mettre en place l'algorithme de base utilisé dans les méthodes de Monte-Carlo pour prédire la valeur d'un état $S_t$ en moyennant les revenus des épisodes :
avec $G_t$ le revenu actuel obtenu à partir de l'instant $t$. Appelons cette méthode la méthode de Monte-Carlo avec $\alpha$ constant.
2.2. Méthode par différences temporelles
Là où les méthodes de Monte-Carlo doivent attendre la fin d'un épisode pour mettre à jour l'équation de récurrence (il faut connaître le revenu $G_t$), les méthodes par différences temporelles n'attendent que le prochain pas de temps. À l'instant $t+1$, l'estimation est faite à partir de la prochaine récompense $R_{t+1}$ et de l'estimation de la prochaine valeur d'état $S_{t+1}$ à l'instant $t+1$:
La cible pour la méthode de Monte-Carlo est $G_t$ alors que pour la méthode des différences temporelle, elle vaut ${{R_{t + 1}} + \gamma {V_n}\left( {{S_{t + 1}}} \right)}$.
Cette méthode est appelée $TD(0)$, ou one-step TD. C'est un cas particulier des méthodes $TD(\alpha)$ et des méthodes n-step TD.
Puisque cette méthode se met à jour en se basant sur une partie de son estimation $V(S_{t+1})$, elle rejoint l'idée déjà vue en programmation dynamique. C'est une méthode qui est dite de bootstrap (elle amorce sa mise à jour avant la fin de l'épisode).
2.3. Algorithme TD(0)
2.4. Retour sur les différences entre les méthodes TD / Monte-Carlo et DP
La valeur de l'état $s$ correspond à l'espérance du gain obtenu sur cet état, c'est-à-dire :
${v_\pi }\left( s \right) = E\left[ {{G_t}|{S_t} = s} \right]$
$\quad\quad\quad=E\left[ {{R_{t + 1}} + \gamma {G_{t + 1}}|{S_t} = s} \right]$
$\quad\quad\quad=E\left[ {{R_{t + 1}} + \gamma {v_\pi }\left( {{S_{t + 1}}} \right)|{S_t} = s} \right]$
Les méthodes de Monte-Carlo utilisent une estimation de la première relation comme cible, alors que les méthodes par différences temporelles utilisent une estimation de la troisième relation.
Dans les méthodes de Monte-Carlo et TD, la valeur d'un état est estimée en se basant sur une transition de l'état courant $S_t$ sur l'état suivant $S_{t+1}$. Les méthodes de Monte-Carlo estiment la valeur de $G_t$ car cette valeur n'est pas connue, et les méthodes par différences temporelles utilisent l'estimation ${{v_\pi }\left( {{S_{t + 1}}} \right)}$. Mais les méthodes TD se basent également sur l'échantillon $R_{t+1}$, ce qui fait qu'en plus d'estimer elles échantillonnent l'environnement.